#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "linkedlist.h"


// 自定义内部函数（一般以 “__” 开头），开辟一个新的节点
struct list_t *__alloc_node(int size, const void *data)
{
    list_t *new_node = malloc(sizeof(list_t));

    if (NULL == new_node)
        return NULL;

    new_node->data = malloc(size); // 给数据开辟空间

    if (NULL == new_node->data) {
        free(new_node);
        new_node = NULL;
        return NULL;
    }

    memcpy(new_node->data, data, size); // 拷贝数据
    new_node->next = NULL;

    return new_node;
}


// 找到某节点的前驱节点
static list_t *__prev_node(const listhead_t *list, const void *key, cmp_t cmp)
{
    list_t *prev = NULL;

    for (prev = (list_t *)(&list->node); prev->next != NULL; prev = prev->next) {
        if (0 == cmp(prev->next->data, key))
            return prev;
    }

    return NULL; // 返回 NULL 表示目标节点不存在
}


// 总相等的比较函数
static int __always_cmp(const void *data, const void *key)
{
    return 0;
}


// 初始化头节点
int listhead_init(listhead_t **list, int size)
{
    if (NULL != *list)
        return -1;

    *list = malloc(sizeof(listhead_t));
    if (NULL == *list)
        return -1;

    (*list)->size = size;
    (*list)->node.data = NULL;
    (*list)->node.next = NULL;

    return 0;
}


// 判断链表是否为空
int list_empty(const listhead_t *list)
{
    return NULL == list->node.next;
}


// 增加节点（头插）
int list_insert(listhead_t *list, const void *data)
{
    list_t *node = __alloc_node(list->size, data);

    if (NULL == node)
        return -1;

    node->next = list->node.next;
    list->node.next = node;

    return 0;
}


// 增加节点（尾插）
int list_insert_tail(listhead_t *list, const void *data)
{
    list_t *node = __alloc_node(list->size, data);
    list_t *pos = NULL;

    if (NULL == node)
        return -1;

    // 找到尾部节点（如果为空就是头节点）
    for (pos = &list->node; pos->next != NULL; pos = pos->next);

    pos->next = node;

    return 0;
}


// 按值查找
void *list_find(const listhead_t *list, const void *key, cmp_t cmp)
{
    list_t *node = __prev_node(list, key, cmp);

    if (NULL == node)
        return NULL;

    return node->next->data; // 返回找到的值
}


// 删除节点
int list_delete(listhead_t *list, const void *key, cmp_t cmp)
{
    list_t *prev = NULL, *del = NULL;

    prev = __prev_node(list, key, cmp); // 找到待删除结点的前驱节点

    if (NULL == prev)
        return -1;

    del = prev->next; // 保存要删除的节点

    prev->next = del->next;
    del->next = NULL;
    free(del->data);
    del->data = NULL;
    free(del);
    del = NULL;

    return 0;
}


// 遍历
void list_traval(const listhead_t *list, pri_t pri)
{
    list_t *node = NULL;

    for (node = (list_t *)list->node.next; node != NULL; node = node->next)
        pri(node->data);

    printf("\n");
}


// 销毁
void list_destroy(listhead_t **list)
{
    while (!list_empty(*list)) // 链表不为空就挨个销毁节点
        list_delete(*list, NULL, __always_cmp);

    free(*list);
    *list = NULL;
}


